package zhengqc.hash_table;

import zhengqc.common.Pair;

import java.util.TreeMap;

public class HashTable<K extends Comparable<K>, V> {
    private static final float UPPER_FACTOR = 1.75f;
    private static final float LOWER_FACTOR = 0.75f;

    private int capacityIndex = 0;
    private TreeMap<K, V>[] table;
    private int M;
    private int size;
    private final int[] capacity = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 };

    public HashTable() {
        this.size = 0;
        this.M = this.capacity[this.capacityIndex];
        this.table = new TreeMap[M];
        for (int i = 0; i < this.M; ++i) {
            this.table[i] = new TreeMap<>();
        }
    }
    private void adjustCapacity(int newCapacity) {
        TreeMap<K, V>[] newTable = new TreeMap[newCapacity];
        for (int i = 0; i < newCapacity; ++i) {
            newTable[i] = new TreeMap<>();
        }
        int oldM = M;
        this.M = newCapacity;
        for (int i = 0; i < oldM; ++i) {
            TreeMap<K, V> map = new TreeMap<>();
            for (K key: map.keySet()) {
                newTable[this.hash(key)].put(key, map.get(key));
            }
        }
        this.table = newTable;
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % M;
    }
    public int getSize() {
        return this.size;
    }
    public void add(K key, V value) {
        TreeMap<K, V> map = this.table[this.hash(key)];
        if ( map.containsKey(key) ) { // 覆盖
            map.put(key, value);
        } else { // 添加
            map.put(key, value);
            ++ this.size;
            if ( (this.size >= UPPER_FACTOR * this.M) && // size / M >= UPPER
                    (this.capacityIndex+1 < this.capacity.length) ) {
                this.capacityIndex += 1;
                this.adjustCapacity(this.capacity[this.capacityIndex]);
            }
        }
    }
    public V remove(K key) {
        TreeMap<K, V> map = this.table[this.hash(key)];
        V ret = null;
        if (map.containsKey(key)) {
            ret = map.remove(key);
            -- this.size;
            if ( (this.size < LOWER_FACTOR * this.M) && // size / M < LOWER
                 (this.capacityIndex - 1 >= 0) ) {
                this.capacityIndex -= 1;
                this.adjustCapacity(this.capacity[this.capacityIndex]);
            }
        }
        return ret;
    }
    public void set(K key, V value) {
        TreeMap<K, V> map = this.table[this.hash(key)];
        if (! map.containsKey(key)) {
            throw new IllegalArgumentException("the key " + key + " is not exist!");
        }
        map.put(key, value);
    }
    public boolean contains(K key) {
        return this.table[this.hash(key)].containsKey(key);
    }
    public V get(K key) {
        return this.table[this.hash(key)].get(key);
    }

    public Pair<K, V>[] toItems() {
        Pair<K, V>[] items = new Pair[this.size];
        int count = 0;
        for (int i = 0; i < this.M; ++i) {
            TreeMap<K, V> map = this.table[i];
            for (K key: map.keySet()) {
                items[count++] = new Pair<>(key, map.get(key));
            }
        }
        return items;
    }
}
